package 回溯法;

import java.util.Arrays;

/**
 * @author hunbird
 */
class Queens {
    int[] x;//当前解
    int n;//皇后个数
    int sum = 0;//当前已找到的可行方案数

    public int totalQueens(int n) {
        this.n = n;
        x = new int[n + 1];
        backTrace(1);
        return sum;
    }

    /**
     * col行这个点，x[row]列这个点，与已经存在的几个皇后，是否符合要求，放到这个位置上，
     *
     * @param row
     * @return
     */
    private boolean place(int row) {
        for (int i = 1; i < row; i++) {
            if (Math.abs(row - i) == Math.abs(x[row] - x[i]) || x[row] == x[i]) {
                return false;
            }
        }
        return true;
    }

    private void backTrace(int t) {
        if (t > n) {
            sum++;
            System.out.println(Arrays.toString(x));
        } else {
            //第t行，遍历所有的节点
            for (int j = 1; j <= n; j++) {
                x[t] = j;
                //如果第j个节点可以放下皇后
                if (place(t)) {
                    //接着放下一个
                    backTrace(t + 1);
                }
            }
        }
    }


}

public class n后问题 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Queens q = new Queens();
        System.out.println(q.totalQueens(6));

    }

}
